/LMAR=0/XLINE=3/FONT#0=BAXL30/FONT#1=BAXM30/FONT#2=BASB30/FONT#3=SUB/FONT#4=SUP/FONT#5=BASL35/FONT#6=NGR25/FONT#7=MATH30/FONT#8=FIX25/FONT#9=GRKB30/FONT#11=ZERO30
␈↓ α∧␈↓␈↓ u1























␈↓ α∧␈↓α␈↓ β⊗CIRCUMSCRIPTION - A FORM OF NON-MONOTONIC REASONING

␈↓ α∧␈↓α␈↓ εεby John McCarthy

␈↓ α∧␈↓α␈↓ ¬⎇Stanford University

␈↓ α∧␈↓Abstract:␈αHumans␈αand␈αintelligent␈αcomputer␈αprograms␈αmust␈αoften␈αjump␈αto␈αthe␈αconclusion␈α
that␈αthe
␈↓ α∧␈↓objects␈α∂they␈α∞can␈α∂determine␈α∞to␈α∂have␈α∞certain␈α∂properties␈α∞or␈α∂relations␈α∞are␈α∂the␈α∞only␈α∂objects␈α∂that␈α∞do.
␈↓ α∧␈↓␈↓↓Circumscription␈↓ formalizes such conjectural reasoning.
␈↓ α∧␈↓␈↓ u2


␈↓ α∧␈↓1. ␈↓αIntroduction - The Qualification Problem␈↓

␈↓ α∧␈↓␈↓ αT(McCarthy␈α∞1960)␈α∞proposed␈α∂a␈α∞program␈α∞with␈α∞"common␈α∂sense"␈α∞that␈α∞would␈α∞represent␈α∂what␈α∞it
␈↓ α∧␈↓knows␈α∩(mainly)␈α∩by␈α⊃sentences␈α∩in␈α∩a␈α∩suitable␈α⊃logical␈α∩language.␈α∩ It␈α∩would␈α⊃decide␈α∩what␈α∩to␈α∩do␈α⊃by
␈↓ α∧␈↓deducing␈α
a␈α
conclusion␈α
that␈α
it␈α
should␈α
perform␈α
a␈α
certain␈α
act.␈α
 Performing␈α
the␈α
act␈α
would␈α
create␈α
a␈α
new
␈↓ α∧␈↓situation,␈α
and␈α
it␈α
would␈α
again␈α
decide␈α
what␈α
to␈α
do.␈α
 This␈α
requires␈α
representing␈α
both␈αknowledge␈α
about
␈↓ α∧␈↓the particular situation and general common sense knowledge as sentences of logic.

␈↓ α∧␈↓␈↓ αTThe␈α∀"qualification␈α∀problem",␈α∀immediately␈α∀arose␈α∀in␈α∀representing␈α∀general␈α∀common␈α∪sense
␈↓ α∧␈↓knowledge.␈α
 It␈α
seemed␈α
that␈α
in␈α
order␈α
to␈α
fully␈α
represent␈α
the␈α
conditions␈α
for␈α
the␈α
successful␈α
performance
␈↓ α∧␈↓of␈αan␈αaction,␈αan␈αimpractical␈αand␈αimplausible␈αnumber␈αof␈αqualifications␈αwould␈αhave␈αto␈αbe␈αincluded
␈↓ α∧␈↓in␈α⊂the␈α⊂sentences␈α⊃expressing␈α⊂them.␈α⊂ For␈α⊃example,␈α⊂the␈α⊂successful␈α⊃use␈α⊂of␈α⊂a␈α⊃boat␈α⊂to␈α⊂cross␈α⊃a␈α⊂river
␈↓ α∧␈↓requires,␈αif␈αthe␈αboat␈αis␈αa␈αrowboat,␈αthat␈αthe␈αoars␈αand␈αrowlocks␈αbe␈αpresent␈αand␈αunbroken,␈α
and␈αthat
␈↓ α∧␈↓they␈α⊃fit␈α∩each␈α⊃other.␈α∩ Many␈α⊃other␈α∩qualifications␈α⊃can␈α∩be␈α⊃added,␈α∩making␈α⊃the␈α∩rules␈α⊃for␈α∩using␈α⊃a
␈↓ α∧␈↓rowboat␈α⊃almost␈α⊃impossible␈α∩to␈α⊃apply,␈α⊃and␈α⊃yet␈α∩anyone␈α⊃will␈α⊃still␈α⊃be␈α∩able␈α⊃to␈α⊃think␈α∩of␈α⊃additional
␈↓ α∧␈↓requirements not yet stated.

␈↓ α∧␈↓␈↓ αTCircumscription␈α⊃is␈α∩a␈α⊃rule␈α∩of␈α⊃conjecture␈α∩that␈α⊃can␈α∩be␈α⊃used␈α∩by␈α⊃a␈α∩person␈α⊃or␈α∩program␈α⊃for
␈↓ α∧␈↓"jumping␈αto␈αcertain␈αconclusions".␈α Namely,␈α␈↓↓the␈αobjects␈αthat␈αcan␈αbe␈αshown␈αto␈αhave␈αa␈αcertain␈αproperty
␈↓ α∧␈↓↓P␈α↔by␈α⊗reasoning␈α↔from␈α⊗certain␈α↔facts␈α⊗A␈α↔are␈α⊗all␈α↔the␈α⊗objects␈α↔that␈α⊗satisfy␈α↔P␈↓.␈α↔ More␈α⊗generally,
␈↓ α∧␈↓circumscription␈α
can␈α
be␈α
used␈αto␈α
conjecture␈α
that␈α
the␈α
tuples␈α␈↓↓<x,y ... ,z>␈↓␈α
that␈α
can␈α
be␈α
shown␈αto␈α
satisfy
␈↓ α∧␈↓a␈α
relation␈α␈↓↓P(x,y, ... ,z)␈↓␈α
are␈αall␈α
the␈α
tuples␈αsatisfying␈α
this␈αrelation.␈α
 Thus␈α
we␈α␈↓↓circumscribe␈↓␈α
the␈αset␈α
of
␈↓ α∧␈↓relevant tuples.

␈↓ α∧␈↓␈↓ αTWe␈α∞can␈α
postulate␈α∞that␈α∞a␈α
boat␈α∞can␈α∞be␈α
used␈α∞to␈α
cross␈α∞a␈α∞river␈α
unless␈α∞"something"␈α∞prevents␈α
it.
␈↓ α∧␈↓Then␈αcircumscription␈αmay␈αbe␈αused␈αto␈αconjecture␈αthat␈αthe␈αonly␈αentities␈αthat␈αcan␈αprevent␈αthe␈αuse␈αof
␈↓ α∧␈↓the␈α∞boat␈α∞are␈α∞those␈α∞whose␈α∞existence␈α∞follows␈α∞from␈α∞the␈α∞facts␈α∞at␈α∞hand.␈α∞ If␈α∞no␈α∞lack␈α∞of␈α∞oars␈α∞or␈α∞other
␈↓ α∧␈↓circumstance␈α⊂preventing␈α⊂boat␈α⊂use␈α⊂is␈α⊂deducible,␈α⊃then␈α⊂the␈α⊂boat␈α⊂is␈α⊂concluded␈α⊂to␈α⊂be␈α⊃usable.␈α⊂ The
␈↓ α∧␈↓correctness␈αof␈αthis␈αconclusion␈αdepends␈αon␈αour␈αhaving␈α"taken␈αinto␈αaccount"␈αall␈αrelevant␈αfacts␈αwhen
␈↓ α∧␈↓we made the circumscription.

␈↓ α∧␈↓␈↓ αTCircumscription␈α∂formalizes␈α∂several␈α∞processes␈α∂of␈α∂human␈α∞informal␈α∂reasoning.␈α∂ For␈α∞example,
␈↓ α∧␈↓common␈αsense␈αreasoning␈αis␈αordinarily␈αready␈αto␈αjump␈αto␈αthe␈αconclusion␈αthat␈αa␈αtool␈αcan␈αbe␈αused␈αfor
␈↓ α∧␈↓its␈α∞intended␈α
purpose␈α∞unless␈α
something␈α∞prevents␈α
its␈α∞use.␈α
 Considered␈α∞purely␈α
extensionally,␈α∞such␈α
a
␈↓ α∧␈↓statement␈α
conveys␈αno␈α
information;␈αit␈α
seems␈α
merely␈αto␈α
assert␈αthat␈α
a␈α
tool␈αcan␈α
be␈αused␈α
for␈αits␈α
intended
␈↓ α∧␈↓purpose␈α
unless␈α
it␈α
can't.␈α
 Heuristically,␈α
the␈α
statement␈α
is␈α
not␈α
just␈α
a␈α
tautologous␈α
disjunction;␈α
it␈α
suggests
␈↓ α∧␈↓forming a plan to use the tool.

␈↓ α∧␈↓␈↓ αTEven␈αwhen␈αa␈αprogram␈αdoes␈αnot␈αreach␈αits␈αconclusions␈αby␈αmanipulating␈αsentences␈αin␈αa␈αformal
␈↓ α∧␈↓language,␈α
we␈αcan␈α
often␈αprofitably␈α
analyze␈αits␈α
behavior␈α
by␈αconsidering␈α
it␈αto␈α
␈↓↓believe␈↓␈αcertain␈α
sentences
␈↓ α∧␈↓when␈α∞it␈α∞is␈α∞in␈α∞certain␈α
states,␈α∞and␈α∞we␈α∞can␈α∞study␈α∞how␈α
these␈α∞␈↓↓ascribed␈α∞beliefs␈↓␈α∞change␈α∞with␈α∞time.␈α
 See
␈↓ α∧␈↓(McCarthy␈α⊂1979a).␈α⊂ When␈α⊂we␈α⊂do␈α⊂such␈α⊃analyses,␈α⊂we␈α⊂again␈α⊂discover␈α⊂that␈α⊂successful␈α⊃people␈α⊂and
␈↓ α∧␈↓programs must jump to such conclusions.



␈↓ α∧␈↓2. ␈↓αThe Need for Non-Monotonic Reasoning␈↓

␈↓ α∧␈↓␈↓ αTWe␈α≡cannot␈α≡get␈α≥circumscriptive␈α≡reasoning␈α≡capability␈α≥by␈α≡adding␈α≡sentences␈α≡to␈α≥an
␈↓ α∧␈↓␈↓ u3


␈↓ α∧␈↓axiomatization␈αor␈αby␈αadding␈αan␈αordinary␈αrule␈αof␈αinference␈αto␈αmathematical␈αlogic.␈α This␈αis␈αbecause
␈↓ α∧␈↓the␈α⊃well␈α⊃known␈α⊃systems␈α⊃of␈α⊃mathematical␈α⊂logic␈α⊃have␈α⊃the␈α⊃following␈α⊃␈↓↓monotonicity␈α⊃property␈↓.␈α⊃ If␈α⊂a
␈↓ α∧␈↓sentence␈α∂␈↓↓q␈↓␈α⊂follows␈α∂from␈α⊂a␈α∂collection␈α∂␈↓↓A␈↓␈α⊂of␈α∂sentences␈α⊂and␈α∂␈↓↓A ⊂ B␈↓,␈α∂then␈α⊂␈↓↓q␈↓␈α∂follows␈α⊂from␈α∂␈↓↓B.␈↓␈α⊂In␈α∂the
␈↓ α∧␈↓notation␈αof␈αproof␈αtheory:␈αif␈α␈↓↓A ␈↓πr␈↓↓ q␈↓␈αand␈α␈↓↓A ⊂ B␈↓,␈αthen␈α␈↓↓B ␈↓πr␈↓↓ q␈↓.␈α Indeed␈αa␈αproof␈αfrom␈αthe␈αpremisses␈α␈↓↓A␈↓␈α
is
␈↓ α∧␈↓a␈αsequence␈αof␈αsentences␈αeach␈αof␈αwhich␈αis␈αa␈αeither␈αa␈αpremiss,␈αan␈αaxiom␈αor␈αfollows␈αfrom␈αa␈αsubset␈αof
␈↓ α∧␈↓the␈α
sentences␈αoccurring␈α
earlier␈α
in␈αthe␈α
proof␈α
by␈αone␈α
of␈αthe␈α
rules␈α
of␈αinference.␈α
 Therefore,␈α
a␈αproof
␈↓ α∧␈↓from␈α
␈↓↓A␈↓␈α
can␈αalso␈α
serve␈α
as␈α
a␈αproof␈α
from␈α
␈↓↓B.␈↓␈αThe␈α
semantic␈α
notion␈α
of␈αentailment␈α
is␈α
also␈αmonotonic;␈α
we
␈↓ α∧␈↓say␈αthat␈α␈↓↓A␈↓␈αentails␈α␈↓↓q␈↓␈α(written␈α␈↓↓A ␈↓πq␈↓↓ q␈↓)␈αif␈α␈↓↓q␈↓␈αis␈αtrue␈αin␈αall␈αmodels␈αof␈α␈↓↓A.␈↓␈αBut␈αif␈α␈↓↓A ␈↓πq␈↓↓ q␈↓␈αand␈α
␈↓↓A ⊂ B␈↓,␈αthen
␈↓ α∧␈↓every model of ␈↓↓B␈↓ is also a model of ␈↓↓A,␈↓ which shows that ␈↓↓B ␈↓πq␈↓↓ q␈↓.

␈↓ α∧␈↓␈↓ αT␈↓↓Circumscription␈↓␈α
is␈α
a␈α
formalized␈α
␈↓↓rule␈α
of␈α
conjecture␈↓␈α
that␈α
can␈α
be␈α
used␈α
along␈α
with␈α
the␈α∞␈↓↓rules␈α
of
␈↓ α∧␈↓↓inference␈↓␈α∪of␈α∪first␈α∩order␈α∪logic.␈α∪ ␈↓↓Predicate␈α∩circumscription␈↓␈α∪assumes␈α∪that␈α∩entities␈α∪satisfy␈α∪a␈α∩given
␈↓ α∧␈↓predicate␈α∩only␈α⊃if␈α∩they␈α∩have␈α⊃to␈α∩on␈α⊃the␈α∩basis␈α∩of␈α⊃a␈α∩collection␈α⊃of␈α∩facts.␈α∩ ␈↓↓Domain␈α⊃circumscription␈↓
␈↓ α∧␈↓conjectures␈α
that␈α
the␈α
"known"␈αentities␈α
are␈α
all␈α
there␈α
are.␈α It␈α
turns␈α
out␈α
that␈α
domain␈αcircumscription,
␈↓ α∧␈↓previously called ␈↓↓minimal inference␈↓, can be subsumed under predicate circumscription.

␈↓ α∧␈↓␈↓ αTWe␈αwill␈αargue␈α
using␈αexamples␈αthat␈α
humans␈αuse␈αsuch␈α
"non-monotonic"␈αreasoning␈αand␈αthat␈α
it
␈↓ α∧␈↓is␈α⊃required␈α⊂for␈α⊃intelligent␈α⊂behavior.␈α⊃ The␈α⊂default␈α⊃case␈α⊂reasoning␈α⊃of␈α⊂many␈α⊃computer␈α⊂programs
␈↓ α∧␈↓(Reiter␈α
1980)␈α
and␈α∞the␈α
use␈α
of␈α∞THNOT␈α
in␈α
MICROPLANNER␈α∞(Sussman,␈α
et.␈α
al.␈α∞ 1971)␈α
programs
␈↓ α∧␈↓are␈α∩also␈α∩examples␈α∩of␈α∩non-monotonic␈α∩reasoning,␈α∪but␈α∩possibly␈α∩of␈α∩a␈α∩different␈α∩kind␈α∪from␈α∩those
␈↓ α∧␈↓discussed in this paper.  (Hewitt 1972) gives the basic ideas of the PLANNER approach.

␈↓ α∧␈↓␈↓ αTThe␈α
result␈α
of␈α
applying␈α
circumscription␈α
to␈α
a␈α
collection␈α
␈↓↓A␈↓␈α
of␈α
facts␈α
is␈α
a␈α
sentence␈α∞schema␈α
that
␈↓ α∧␈↓asserts␈α∞that␈α∞the␈α
only␈α∞tuples␈α∞satisfying␈α∞a␈α
predicate␈α∞␈↓↓P(x, ... ,z)␈↓␈α∞are␈α
those␈α∞whose␈α∞doing␈α∞so␈α
follows
␈↓ α∧␈↓from␈α∂the␈α∂sentences␈α∂of␈α∂␈↓↓A.␈↓␈α∞Since␈α∂adding␈α∂more␈α∂sentences␈α∂to␈α∞␈↓↓A␈↓␈α∂might␈α∂make␈α∂␈↓↓P␈↓␈α∂applicable␈α∂to␈α∞more
␈↓ α∧␈↓tuples,␈α≠circumscription␈α≠is␈α≠not␈α~monotonic.␈α≠ Conclusions␈α≠derived␈α≠from␈α≠circumscription␈α~are
␈↓ α∧␈↓conjectures␈αthat␈α
␈↓↓A␈↓␈αincludes␈αall␈α
the␈αrelevant␈α
facts␈αand␈αthat␈α
the␈αobjects␈α
whose␈αexistence␈αfollows␈α
from
␈↓ α∧␈↓␈↓↓A␈↓ are all the relevant objects.

␈↓ α∧␈↓␈↓ αTA␈α
heuristic␈α∞program␈α
might␈α∞use␈α
circumscription␈α∞in␈α
various␈α∞ways.␈α
 Suppose␈α∞it␈α
circumscribes
␈↓ α∧␈↓some␈αfacts␈αand␈αmakes␈αa␈αplan␈αon␈αthe␈αbasis␈αof␈αthe␈αconclusions␈αreached.␈α It␈αmight␈αimmediately␈αcarry
␈↓ α∧␈↓out the plan, or be more cautious and look for additional facts that might require modifying it.

␈↓ α∧␈↓␈↓ αTBefore␈α∩introducing␈α∩the␈α∩formalism,␈α∩we␈α∪informally␈α∩discuss␈α∩a␈α∩well␈α∩known␈α∪problem␈α∩whose
␈↓ α∧␈↓solution seems to involve such non-monotonic reasoning.



␈↓ α∧␈↓3. ␈↓αMissionaries and Cannibals␈↓

␈↓ α∧␈↓␈↓ αTThe␈α
␈↓↓Missionaries␈αand␈α
Cannibals␈↓␈α
puzzle,␈αmuch␈α
used␈αin␈α
AI,␈α
contains␈αmore␈α
than␈αenough␈α
detail
␈↓ α∧␈↓to illustrate many of the issues.

␈↓ α∧␈↓␈↓ αT␈↓↓"Three␈α∪missionaries␈α∀and␈α∪three␈α∀cannibals␈α∪come␈α∀to␈α∪a␈α∪river.␈α∀ A␈α∪rowboat␈α∀that␈α∪seats␈α∀two␈α∪is
␈↓ α∧␈↓↓available.␈α∪ If␈α∩the␈α∪cannibals␈α∩ever␈α∪outnumber␈α∪the␈α∩missionaries␈α∪on␈α∩either␈α∪bank␈α∩of␈α∪the␈α∪river,␈α∩the
␈↓ α∧␈↓↓missionaries will be eaten.  How shall they cross the river?"␈↓.

␈↓ α∧␈↓␈↓ αTObviously␈α
the␈α∞puzzler␈α
is␈α
expected␈α∞to␈α
devise␈α
a␈α∞strategy␈α
of␈α
rowing␈α∞the␈α
boat␈α
back␈α∞and␈α
forth
␈↓ α∧␈↓that gets them all across and avoids the disaster.
␈↓ α∧␈↓␈↓ u4


␈↓ α∧␈↓␈↓ αTAmarel␈α∩(1971)␈α∩considered␈α∩several␈α∩representations␈α⊃of␈α∩the␈α∩problem␈α∩and␈α∩discussed␈α⊃criteria
␈↓ α∧␈↓whereby␈α⊂the␈α⊃following␈α⊂representation␈α⊂is␈α⊃preferred␈α⊂for␈α⊂purposes␈α⊃of␈α⊂AI,␈α⊂because␈α⊃it␈α⊂leads␈α⊃to␈α⊂the
␈↓ α∧␈↓smallest␈αstate␈αspace␈αthat␈αmust␈αbe␈αexplored␈αto␈αfind␈αthe␈αsolution.␈α A␈αstate␈αis␈αa␈αtriple␈αcomprising␈αthe
␈↓ α∧␈↓numbers␈αof␈αmissionaries,␈αcannibals␈αand␈αboats␈αon␈αthe␈αstarting␈αbank␈αof␈αthe␈αriver.␈α The␈αinitial␈αstate
␈↓ α∧␈↓is␈α≤331,␈α≤the␈α≤desired␈α≤final␈α≤state␈α≤is␈α≤000,␈α≤and␈α≤one␈α≤solution␈α≤is␈α≤given␈α≤by␈α≤the␈α≠sequence
␈↓ α∧␈↓(331,220,321,300,311,110,221,020,031,010,021,000).

␈↓ α∧␈↓␈↓ αTWe␈α⊂are␈α⊂not␈α⊂presently␈α⊂concerned␈α⊂with␈α⊂the␈α⊂heuristics␈α⊂of␈α⊂the␈α⊂problem␈α⊂but␈α⊂rather␈α⊂with␈α⊂the
␈↓ α∧␈↓correctness␈αof␈αthe␈αreasoning␈αthat␈α
goes␈αfrom␈αthe␈αEnglish␈αstatement␈α
of␈αthe␈αproblem␈αto␈αAmarel's␈α
state
␈↓ α∧␈↓space␈α
representation.␈α
 A␈α∞generally␈α
intelligent␈α
computer␈α∞program␈α
should␈α
be␈α∞able␈α
to␈α
carry␈α∞out␈α
this
␈↓ α∧␈↓reasoning.␈α⊃ Of␈α⊃course,␈α⊃there␈α⊃are␈α⊃the␈α⊃well␈α⊃known␈α⊃difficulties␈α⊃in␈α⊃making␈α⊃computers␈α⊂understand
␈↓ α∧␈↓English,␈α⊃but␈α⊃suppose␈α⊃the␈α⊃English␈α⊃sentences␈α⊃describing␈α⊃the␈α⊃problem␈α⊃have␈α⊃already␈α⊃been␈α⊃rather
␈↓ α∧␈↓directly␈α⊂translated␈α⊂into␈α⊂first␈α⊂order␈α⊂logic.␈α⊂ The␈α⊂correctness␈α⊂of␈α⊂Amarel's␈α⊂representation␈α⊂is␈α⊃not␈α⊂an
␈↓ α∧␈↓ordinary logical consequence of these sentences for two further reasons.

␈↓ α∧␈↓␈↓ αTFirst,␈α∞nothing␈α∞has␈α∞been␈α∞stated␈α∞about␈α∞the␈α∞properties␈α∞of␈α∞boats␈α∞or␈α∞even␈α∞the␈α∞fact␈α∞that␈α
rowing
␈↓ α∧␈↓across␈α∞the␈α∞river␈α
doesn't␈α∞change␈α∞the␈α∞numbers␈α
of␈α∞missionaries␈α∞or␈α∞cannibals␈α
or␈α∞the␈α∞capacity␈α∞of␈α
the
␈↓ α∧␈↓boat.␈α Indeed␈αit␈αhasn't␈αbeen␈αstated␈αthat␈αsituations␈αchange␈αas␈αa␈αresult␈αof␈αaction.␈α These␈αfacts␈αfollow
␈↓ α∧␈↓from␈α∞common␈α∞sense␈α∞knowledge,␈α∞so␈α∞let␈α∞us␈α
imagine␈α∞that␈α∞common␈α∞sense␈α∞knowledge,␈α∞or␈α∞at␈α∞least␈α
the
␈↓ α∧␈↓relevant part of it, is also expressed in first order logic.

␈↓ α∧␈↓␈↓ αTThe␈α∩second␈α⊃reason␈α∩we␈α⊃can't␈α∩␈↓↓deduce␈↓␈α∩the␈α⊃propriety␈α∩of␈α⊃Amarel's␈α∩representation␈α∩is␈α⊃deeper.
␈↓ α∧␈↓Imagine␈α
giving␈α
someone␈α
the␈α
problem,␈α
and␈α
after␈αhe␈α
puzzles␈α
for␈α
a␈α
while,␈α
he␈α
suggests␈αgoing␈α
upstream
␈↓ α∧␈↓half␈α
a␈α
mile␈α
and␈α
crossing␈α
on␈α
a␈α
bridge.␈α∞ "What␈α
bridge",␈α
you␈α
say.␈α
 "No␈α
bridge␈α
is␈α
mentioned␈α∞in␈α
the
␈↓ α∧␈↓statement␈αof␈α
the␈αproblem."␈αAnd␈α
this␈αdunce␈αreplies,␈α
"Well,␈αthey␈α
don't␈αsay␈αthere␈α
isn't␈αa␈αbridge".␈α
 You
␈↓ α∧␈↓look␈αat␈αthe␈αEnglish␈αand␈αeven␈αat␈αthe␈αtranslation␈αof␈αthe␈αEnglish␈αinto␈αfirst␈αorder␈αlogic,␈αand␈αyou␈αmust
␈↓ α∧␈↓admit␈αthat␈α
"they␈αdon't␈αsay"␈α
there␈αis␈αno␈α
bridge.␈α So␈αyou␈α
modify␈αthe␈αproblem␈α
to␈αexclude␈αbridges␈α
and
␈↓ α∧␈↓pose␈α∂it␈α∂again,␈α∂and␈α∂the␈α∂dunce␈α∂proposes␈α∂a␈α∂helicopter,␈α∂and␈α∂after␈α∂you␈α∂exclude␈α∂that,␈α∂he␈α∂proposes␈α∂a
␈↓ α∧␈↓winged horse or that the others hang onto the outside of the boat while two row.

␈↓ α∧␈↓␈↓ αTYou␈α
now␈α∞see␈α
that␈α
while␈α∞a␈α
dunce,␈α∞he␈α
is␈α
an␈α∞inventive␈α
dunce.␈α
 Despairing␈α∞of␈α
getting␈α∞him␈α
to
␈↓ α∧␈↓accept␈α⊂the␈α⊂problem␈α⊂in␈α⊂the␈α⊂proper␈α⊂puzzler's␈α⊂spirit,␈α⊂you␈α⊂tell␈α⊂him␈α⊂the␈α⊂solution.␈α⊂ To␈α⊃your␈α⊂further
␈↓ α∧␈↓annoyance,␈αhe␈αattacks␈αyour␈αsolution␈αon␈αthe␈αgrounds␈αthat␈αthe␈αboat␈αmight␈αhave␈αa␈αleak␈αor␈αlack␈αoars.
␈↓ α∧␈↓After␈αyou␈αrectify␈αthat␈αomission␈αfrom␈αthe␈αstatement␈αof␈αthe␈αproblem,␈αhe␈αsuggests␈αthat␈αa␈αsea␈αmonster
␈↓ α∧␈↓may␈αswim␈αup␈αthe␈αriver␈αand␈αmay␈αswallow␈αthe␈αboat.␈α Again␈αyou␈αare␈αfrustrated,␈αand␈αyou␈αlook␈αfor␈αa
␈↓ α∧␈↓mode of reasoning that will settle his hash once and for all.

␈↓ α∧␈↓␈↓ αTIn␈αspite␈α
of␈αour␈α
irritation␈αwith␈αthe␈α
dunce,␈αit␈α
would␈αbe␈αcheating␈α
to␈αput␈α
into␈αthe␈α
statement␈αof
␈↓ α∧␈↓the␈α
problem␈α
that␈α
there␈α
is␈α
no␈αother␈α
way␈α
to␈α
cross␈α
the␈α
river␈αthan␈α
using␈α
the␈α
boat␈α
and␈α
that␈αnothing␈α
can
␈↓ α∧␈↓go␈αwrong␈α
with␈αthe␈α
boat.␈α A␈αhuman␈α
doesn't␈αneed␈α
such␈αan␈αad␈α
hoc␈αnarrowing␈α
of␈αthe␈α
problem,␈αand
␈↓ α∧␈↓indeed␈αthe␈αonly␈αwatertight␈αway␈αto␈αdo␈αit␈αmight␈αamount␈αto␈αspecifying␈αthe␈αAmarel␈αrepresentation␈αin
␈↓ α∧␈↓English.␈α Rather␈α
we␈αwant␈αto␈α
avoid␈αthe␈α
excessive␈αqualification␈αand␈α
get␈αthe␈α
Amarel␈αrepresentation
␈↓ α∧␈↓by common sense reasoning as humans ordinarily do.

␈↓ α∧␈↓␈↓ αTCircumscription␈αis␈αone␈αcandidate␈αfor␈αaccomplishing␈αthis.␈α It␈αwill␈αallow␈αus␈αto␈αconjecture␈αthat
␈↓ α∧␈↓no␈α∩relevant␈α∩objects␈α⊃exist␈α∩in␈α∩certain␈α⊃categories␈α∩except␈α∩those␈α⊃whose␈α∩existence␈α∩follows␈α∩from␈α⊃the
␈↓ α∧␈↓statement␈α∂of␈α∂the␈α∂problem␈α∞and␈α∂common␈α∂sense␈α∂knowledge.␈α∞ When␈α∂we␈α∂␈↓↓circumscribe␈↓␈α∂the␈α∂first␈α∞order
␈↓ α∧␈↓logic␈α
statement␈αof␈α
the␈α
problem␈αtogether␈α
with␈α
the␈αcommon␈α
sense␈αfacts␈α
about␈α
boats␈αetc.,␈α
we␈α
will␈αbe
␈↓ α∧␈↓able␈α∞to␈α
conclude␈α∞that␈α∞there␈α
is␈α∞no␈α∞bridge␈α
or␈α∞helicopter.␈α∞ "Aha",␈α
you␈α∞say,␈α∞"but␈α
there␈α∞won't␈α∞be␈α
any
␈↓ α∧␈↓␈↓ u5


␈↓ α∧␈↓oars␈αeither".␈α No,␈αwe␈αget␈αout␈αof␈αthat␈αas␈αfollows:␈αIt␈αis␈αa␈αpart␈αof␈αcommon␈αknowledge␈αthat␈αa␈αboat␈αcan
␈↓ α∧␈↓be␈αused␈αto␈α
cross␈αa␈αriver␈α
␈↓↓unless␈αthere␈αis␈α
something␈αwrong␈αwith␈α
it␈αor␈αsomething␈α
else␈αprevents␈αusing␈α
it␈↓,
␈↓ α∧␈↓and␈α⊗if␈α⊗our␈α∃facts␈α⊗don't␈α⊗require␈α⊗that␈α∃there␈α⊗be␈α⊗something␈α∃that␈α⊗prevents␈α⊗crossing␈α⊗the␈α∃river,
␈↓ α∧␈↓circumscription␈αwill␈α
generate␈αthe␈α
conjecture␈αthat␈α
there␈αisn't.␈α
 The␈αprice␈α
is␈αintroducing␈α
as␈αentities␈α
in
␈↓ α∧␈↓our language the "somethings" that may prevent the use of the boat.

␈↓ α∧␈↓␈↓ αTIf␈α
the␈αstatement␈α
of␈α
the␈αproblem␈α
were␈α
extended␈αto␈α
mention␈α
a␈αbridge,␈α
then␈αthe␈α
circumscription
␈↓ α∧␈↓of␈α∞the␈α∞problem␈α∞statement␈α∞would␈α∞no␈α∞longer␈α∂permit␈α∞showing␈α∞the␈α∞non-existence␈α∞of␈α∞a␈α∞bridge,␈α∂i.e.␈α∞a
␈↓ α∧␈↓conclusion␈α
that␈α
can␈α
be␈α∞drawn␈α
from␈α
a␈α
smaller␈α∞collection␈α
of␈α
facts␈α
can␈α∞no␈α
longer␈α
be␈α
drawn␈α∞from␈α
a
␈↓ α∧␈↓larger.␈α∞ This␈α∞non-monotonic␈α∞character␈α∞of␈α∞circumscription␈α∞is␈α
just␈α∞what␈α∞we␈α∞want␈α∞for␈α∞this␈α∞kind␈α
of
␈↓ α∧␈↓problem.␈α∞ The␈α∞statement,␈α∞␈↓↓"There␈α∞is␈α∞a␈α∞bridge␈α∞a␈α
mile␈α∞upstream,␈α∞and␈α∞the␈α∞boat␈α∞has␈α∞a␈α∞leak."␈↓␈α
doesn't
␈↓ α∧␈↓contradict the text of the problem, but its addition invalidates the Amarel representation.

␈↓ α∧␈↓␈↓ αTIn␈αthe␈αusual␈αsort␈αof␈αpuzzle,␈αthere␈αis␈αa␈αconvention␈αthat␈αthere␈αis␈αno␈αadditional␈αobjects␈αbeyond
␈↓ α∧␈↓those␈αmentioned␈αin␈αthe␈αpuzzle␈αor␈αwhose␈αexistence␈αis␈αdeducible␈αfrom␈αthe␈αpuzzle␈αand␈αcommon␈αsense
␈↓ α∧␈↓knowledge.␈α The␈αconvention␈αcan␈αbe␈αexplicated␈α
as␈αapplying␈αcircumscription␈αto␈αthe␈αpuzzle␈α
statement
␈↓ α∧␈↓and␈α∞a␈α∞certain␈α∞part␈α∞of␈α∞common␈α∞sense␈α∞knowledge.␈α∞ However,␈α∞if␈α∞one␈α∞really␈α∞were␈α∞sitting␈α∞by␈α∞a␈α
river
␈↓ α∧␈↓bank␈α→and␈α_these␈α→six␈α_people␈α→came␈α→by␈α_and␈α→posed␈α_their␈α→problem,␈α_one␈α→wouldn't␈α→take␈α_the
␈↓ α∧␈↓circumscription␈αfor␈αgranted,␈αbut␈αone␈α␈↓↓would␈↓␈α
consider␈αthe␈αresult␈αof␈αcircumscription␈αas␈α
a␈αhypothesis.
␈↓ α∧␈↓In puzzles, circumscription seems to be a rule of inference, while in life it is a rule of conjecture.

␈↓ α∧␈↓␈↓ αTSome␈α∂have␈α∂suggested␈α∂that␈α∂the␈α∂difficulties␈α∂might␈α∂be␈α∂avoided␈α∂by␈α∂introducing␈α∂probabilities.
␈↓ α∧␈↓They␈α∪suggest␈α∪that␈α∪the␈α∪existence␈α∪of␈α∩a␈α∪bridge␈α∪is␈α∪improbable.␈α∪ The␈α∪whole␈α∪situation␈α∩involving
␈↓ α∧␈↓cannibals␈αwith␈αthe␈αpostulated␈αproperties␈αcannot␈αbe␈αregarded␈αas␈αhaving␈αa␈αprobability,␈αso␈αit␈αis␈αhard
␈↓ α∧␈↓to␈αtake␈αseriously␈αthe␈αconditional␈αprobability␈αof␈αa␈αbridge␈αgiven␈αthe␈αhypotheses.␈α More␈αto␈αthe␈αpoint,
␈↓ α∧␈↓we␈α⊂mentally␈α∂propose␈α⊂to␈α∂ourselves␈α⊂the␈α∂normal␈α⊂non-bridge␈α∂non-sea-monster␈α⊂interpretation␈α∂␈↓↓before␈↓
␈↓ α∧␈↓considering␈α∞these␈α∞extraneous␈α∞possibilities,␈α∞let␈α∞alone␈α∞their␈α∞probabilities,␈α∞i.e.␈α∞we␈α∞usually␈α∞don't␈α∞even
␈↓ α∧␈↓introduce␈α∂the␈α∞sample␈α∂space␈α∞in␈α∂which␈α∂these␈α∞possibilities␈α∂are␈α∞assigned␈α∂whatever␈α∂probabilities␈α∞one
␈↓ α∧␈↓might␈αconsider␈αthem␈αto␈αhave.␈α Therefore,␈αregardless␈αof␈αour␈αknowledge␈αof␈αprobabilities,␈αwe␈αneed␈αa
␈↓ α∧␈↓way␈α⊂of␈α⊃formulating␈α⊂the␈α⊂normal␈α⊃situation␈α⊂from␈α⊃the␈α⊂statement␈α⊂of␈α⊃the␈α⊂facts,␈α⊃and␈α⊂non-monotonic
␈↓ α∧␈↓reasoning seems to be required.  The same considerations seem to apply to fuzzy logic.

␈↓ α∧␈↓␈↓ αTUsing␈α
circumscription␈α
requires␈α
that␈α
common␈α
sense␈α
knowledge␈α
be␈α
expressed␈α
in␈α
a␈α∞form␈α
that
␈↓ α∧␈↓says␈α∩a␈α⊃boat␈α∩can␈α∩be␈α⊃used␈α∩to␈α∩cross␈α⊃rivers␈α∩unless␈α∩there␈α⊃is␈α∩something␈α∩that␈α⊃prevents␈α∩its␈α∩use.␈α⊃ In
␈↓ α∧␈↓particular,␈αit␈αlooks␈αlike␈αwe␈αmust␈αintroduce␈αinto␈αour␈α␈↓↓ontology␈↓␈α(the␈αthings␈αthat␈αexist)␈αa␈αcategory␈αthat
␈↓ α∧␈↓includes␈α
␈↓↓something␈α
wrong␈α∞with␈α
a␈α
boat␈↓␈α
or␈α∞a␈α
category␈α
that␈α
includes␈α∞␈↓↓something␈α
that␈α
may␈α∞prevent␈α
its
␈↓ α∧␈↓↓use␈↓.␈α
 Incidentally,␈αonce␈α
we␈α
have␈αdecided␈α
to␈αadmit␈α
␈↓↓something␈α
wrong␈αwith␈α
the␈α
boat␈↓,␈αwe␈α
are␈αinclined␈α
to
␈↓ α∧␈↓admit␈α
a␈α
␈↓↓lack␈α
of␈αoars␈↓␈α
as␈α
such␈α
a␈αsomething␈α
and␈α
to␈α
ask␈αquestions␈α
like,␈α
␈↓↓"Is␈α
a␈αlack␈α
of␈α
oars␈α
all␈α
that␈αis
␈↓ α∧␈↓↓wrong with the boat?␈↓".

␈↓ α∧␈↓␈↓ αTSome␈α⊃philosophers␈α⊃and␈α∩scientists␈α⊃may␈α⊃be␈α⊃reluctant␈α∩to␈α⊃introduce␈α⊃such␈α⊃␈↓↓things,␈↓␈α∩but␈α⊃since
␈↓ α∧␈↓ordinary␈α
language␈α
allows␈α
␈↓↓"something␈α∞wrong␈α
with␈α
the␈α
boat"␈↓␈α
we␈α∞shouldn't␈α
be␈α
hasty␈α
in␈α∞excluding␈α
it.
␈↓ α∧␈↓Making␈α∀a␈α∀suitable␈α∀formalism␈α∀is␈α∀likely␈α∀to␈α∀be␈α∀technically␈α∀difficult␈α∀as␈α∀well␈α∀as␈α∀philosophically
␈↓ α∧␈↓problematical, but we must try.

␈↓ α∧␈↓␈↓ αTWe␈α⊃challenge␈α⊂anyone␈α⊃who␈α⊃thinks␈α⊂he␈α⊃can␈α⊃avoid␈α⊂such␈α⊃entities␈α⊃to␈α⊂express␈α⊃in␈α⊃his␈α⊂favorite
␈↓ α∧␈↓formalism,␈α
␈↓↓"Besides␈αleakiness,␈α
there␈α
is␈αsomething␈α
else␈α
wrong␈αwith␈α
the␈α
boat"␈↓.␈α A␈α
good␈αsolution␈α
would
␈↓ α∧␈↓avoid counterfactuals as this one does.
␈↓ α∧␈↓␈↓ u6


␈↓ α∧␈↓␈↓ αTCircumscription␈α∪may␈α∪help␈α∪understand␈α∪natural␈α∩language,␈α∪because␈α∪if␈α∪the␈α∪use␈α∪of␈α∩natural
␈↓ α∧␈↓language␈α⊃involves␈α⊃something␈α∩like␈α⊃circumscription,␈α⊃it␈α⊃is␈α∩understandable␈α⊃that␈α⊃the␈α∩expression␈α⊃of
␈↓ α∧␈↓general␈α⊃common␈α⊂sense␈α⊃facts␈α⊂in␈α⊃natural␈α⊃language␈α⊂will␈α⊃be␈α⊂difficult␈α⊃without␈α⊂some␈α⊃form␈α⊃of␈α⊂non-
␈↓ α∧␈↓monotonic reasoning.



␈↓ α∧␈↓4. ␈↓αThe Formalism of Circumscription␈↓

␈↓ α∧␈↓␈↓ αTLet␈α␈↓↓A␈↓␈αbe␈αa␈αsentence␈αof␈αfirst␈αorder␈αlogic␈αcontaining␈αa␈αpredicate␈αsymbol␈α␈↓↓P(x␈↓β1␈↓↓, ... ,x␈↓βn␈↓↓)␈↓␈αwhich
␈↓ α∧␈↓we␈α∞will␈α∞write␈α∞␈↓↓P(␈↓¬␈↓↓x)␈↓.␈α∞ We␈α∞write␈α∞␈↓↓A(␈↓	F␈↓↓)␈↓␈α∞for␈α∞the␈α
result␈α∞of␈α∞replacing␈α∞all␈α∞occurrences␈α∞of␈α∞␈↓↓P␈↓␈α∞in␈α∞␈↓↓A␈↓␈α∞by␈α
the
␈↓ α∧␈↓predicate␈α∩expression␈α⊃␈↓	F␈↓.␈α∩ (As␈α⊃well␈α∩as␈α⊃predicate␈α∩symbols,␈α⊃suitable␈α∩λ-expressions␈α⊃are␈α∩allowed␈α⊃as
␈↓ α∧␈↓predicate expressions).

␈↓ α∧␈↓␈↓αDefinition: The circumscription of ␈↓↓P␈↓α in ␈↓↓A(P)␈↓α is the sentence schema␈↓

␈↓ α∧␈↓1)␈↓ αt ␈↓↓A(␈↓	F␈↓↓) ∧ ∀␈↓¬␈↓↓x.(␈↓	F␈↓↓(␈↓¬␈↓↓x) ⊃ P(␈↓¬␈↓↓x))  ⊃  ∀␈↓¬␈↓↓x.(P(␈↓¬␈↓↓x) ⊃ ␈↓	F␈↓↓(␈↓¬␈↓↓x))␈↓.

␈↓ α∧␈↓␈↓ αT(1)␈αcan␈α
be␈αregarded␈αas␈α
asserting␈αthat␈α
the␈αonly␈αtuples␈α
␈↓↓(␈↓¬␈↓↓x)␈↓␈αthat␈α
satisfy␈α␈↓↓P␈↓␈αare␈α
those␈αthat␈αhave␈α
to
␈↓ α∧␈↓-␈α⊂assuming␈α⊂the␈α⊂sentence␈α⊂␈↓↓A.␈↓␈α⊂Namely,␈α⊂(1)␈α⊂contains␈α⊂a␈α⊂predicate␈α⊂parameter␈α⊂␈↓	F␈↓␈α⊂for␈α⊂which␈α⊃we␈α⊂may
␈↓ α∧␈↓subsitute␈α
an␈α
arbitrary␈α
predicate␈α
expression.␈α
 (If␈α
we␈αwere␈α
using␈α
second␈α
order␈α
logic,␈α
there␈α
would␈αbe␈α
a
␈↓ α∧␈↓quantifier␈α
∀␈↓	F␈↓␈α
in␈αfront␈α
of␈α
(1)).␈α Since␈α
(1)␈α
is␈α
an␈αimplication,␈α
we␈α
can␈αassume␈α
both␈α
conjuncts␈α
on␈αthe
␈↓ α∧␈↓left,␈α∂and␈α∂(1)␈α∂lets␈α∂us␈α∂conclude␈α∂the␈α⊂sentence␈α∂on␈α∂the␈α∂right.␈α∂ The␈α∂first␈α∂conjunct␈α∂␈↓↓A(␈↓	F␈↓↓)␈↓␈α⊂expresses␈α∂the
␈↓ α∧␈↓assumption␈α∀that␈α∀␈↓	F␈↓␈α∪satisfies␈α∀the␈α∀conditions␈α∪satisfied␈α∀by␈α∀␈↓↓P,␈↓␈α∪and␈α∀the␈α∀second␈α∪␈↓↓∀␈↓¬␈↓↓x.(␈↓	F␈↓↓(␈↓¬␈↓↓x) ⊃ P(␈↓¬␈↓↓x))␈↓
␈↓ α∧␈↓expresses␈α
the␈α
assumption␈α
that␈α
the␈α
entities␈α
satisfying␈α
␈↓	F␈↓␈α
are␈α
a␈α
subset␈α
of␈α
those␈α
that␈α
satisfy␈α∞␈↓↓P.␈↓␈α
The
␈↓ α∧␈↓conclusion␈α
asserts␈α
the␈α∞converse␈α
of␈α
the␈α∞second␈α
conjunct␈α
which␈α
tells␈α∞us␈α
that␈α
in␈α∞this␈α
case,␈α
␈↓	F␈↓␈α∞and␈α
␈↓↓P␈↓
␈↓ α∧␈↓must coincide.

␈↓ α∧␈↓␈↓ αTWe␈α∪write␈α∪␈↓↓A ␈↓πr␈↓↓␈↓βP␈↓↓ q␈↓␈α∪if␈α∀the␈α∪sentence␈α∪␈↓↓q␈↓␈α∪can␈α∪be␈α∀obtained␈α∪by␈α∪deduction␈α∪from␈α∪the␈α∀result␈α∪of
␈↓ α∧␈↓circumscribing␈α␈↓↓P␈↓␈αin␈α␈↓↓A.␈↓␈αAs␈αwe␈αshall␈αsee␈α␈↓↓␈↓πr␈↓↓␈↓βP␈↓␈αis␈αa␈αnon-monotonic␈αform␈αof␈αinference,␈αwhich␈αwe␈αshall
␈↓ α∧␈↓call ␈↓↓circumscriptive inference␈↓.

␈↓ α∧␈↓␈↓ αTA␈α_slight␈α_generalization␈α_allows␈α_circumscribing␈α_several␈α_predicates␈α_jointly;␈α_thus␈α_jointly
␈↓ α∧␈↓circumscribing ␈↓↓P␈↓ and ␈↓↓Q␈↓ in ␈↓↓A(P,Q)␈↓ leads to

␈↓ α∧␈↓2)␈↓ αt ␈↓↓A(␈↓	F␈↓↓,␈↓	Y␈↓↓) ∧ ∀␈↓¬␈↓↓x.(␈↓	F␈↓↓(␈↓¬␈↓↓x) ⊃ P(␈↓¬␈↓↓x)) ∧ ∀␈↓¬␈↓↓y.(␈↓	Y␈↓↓(␈↓¬␈↓↓y) ⊃ Q(␈↓¬␈↓↓y))  ⊃  ∀␈↓¬␈↓↓x.(P(␈↓¬␈↓↓x) ⊃ ␈↓	F␈↓↓(␈↓¬␈↓↓x)) ∧ ∀␈↓¬␈↓↓y.(Q(␈↓¬␈↓↓y) ⊃ ␈↓	Y␈↓↓(␈↓¬␈↓↓y))␈↓

␈↓ α∧␈↓in␈α∞which␈α∞we␈α∞can␈α∞simultaneously␈α∞substitute␈α∞for␈α∞␈↓	F␈↓␈α∞and␈α∞␈↓	Y␈↓.␈α∞ The␈α∞relation␈α∞␈↓↓A ␈↓πr␈↓↓␈↓βP,Q␈↓↓ q␈↓␈α∞is␈α∞defined␈α∞in␈α
a
␈↓ α∧␈↓corresponding␈α
way.␈α
 Although␈α
we␈α
don't␈α
give␈αexamples␈α
of␈α
joint␈α
circumscription␈α
in␈α
this␈α
paper,␈αwe
␈↓ α∧␈↓believe it will be important in some AI applications.

␈↓ α∧␈↓␈↓ αTConsider the following examples:

␈↓ α∧␈↓␈↓ αT1. In the blocks world, the sentence ␈↓↓A␈↓ may be

␈↓ α∧␈↓3)␈↓ αt ␈↓↓isblock A ∧ isblock B ∧ isblock C␈↓

␈↓ α∧␈↓asserting that ␈↓↓A,␈↓ ␈↓↓B␈↓ and ␈↓↓C␈↓ are blocks.  Circumscribing ␈↓↓isblock␈↓ in (3) gives the schema

␈↓ α∧␈↓4)␈↓ αt ␈↓↓␈↓	F␈↓↓(A) ∧ ␈↓	F␈↓↓(B) ∧ ␈↓	F␈↓↓(C) ∧ ∀x.(␈↓	F␈↓↓(x) ⊃ isblock x)  ⊃  ∀x.(isblock x ⊃ ␈↓	F␈↓↓(x))␈↓.
␈↓ α∧␈↓␈↓ u7


␈↓ α∧␈↓If we now substitute

␈↓ α∧␈↓5)␈↓ αt ␈↓↓␈↓	F␈↓↓(x) ≡ (x = A ∨ x = B ∨ x = C)␈↓

␈↓ α∧␈↓into (4) and use (3), the left side of the implication is seen to be true, and this gives

␈↓ α∧␈↓6)␈↓ αt ␈↓↓∀x.(isblock x ⊃ (x = A ∨ x = B ∨ x = C))␈↓,

␈↓ α∧␈↓which␈αasserts␈α
that␈αthe␈α
only␈αblocks␈αare␈α
␈↓↓A,␈↓␈α␈↓↓B␈↓␈α
and␈α␈↓↓C,␈↓␈α
i.e.␈αjust␈αthose␈α
objects␈αthat␈α
(3)␈αrequires␈α
to␈αbe
␈↓ α∧␈↓blocks.␈α
 This␈αexample␈α
is␈αrather␈α
trivial,␈α
because␈α(3)␈α
provides␈αno␈α
way␈α
of␈αgenerating␈α
new␈αblocks␈α
from
␈↓ α∧␈↓old␈α
ones.␈α
 However,␈α∞it␈α
shows␈α
that␈α∞circumscriptive␈α
inference␈α
is␈α∞non-monotonic␈α
since␈α
if␈α∞we␈α
adjoin
␈↓ α∧␈↓␈↓↓isblock D␈↓ to (3), we will no longer be able to infer (6).

␈↓ α∧␈↓␈↓ αT2. Circumscribing the disjunction

␈↓ α∧␈↓7)␈↓ αt ␈↓↓isblock A ∨ isblock B␈↓

␈↓ α∧␈↓leads to

␈↓ α∧␈↓8)␈↓ αt ␈↓↓(␈↓	F␈↓↓(A) ∨ ␈↓	F␈↓↓(B)) ∧ ∀x.(␈↓	F␈↓↓(x) ⊃ isblock x)  ⊃  ∀x.(isblock x ⊃ ␈↓	F␈↓↓(x))␈↓.

␈↓ α∧␈↓We may then substitute successively ␈↓↓␈↓	F␈↓↓(x) ≡ (x=A)␈↓ and ␈↓↓␈↓	F␈↓↓(x) ≡ (x=B)␈↓, and these give respectively

␈↓ α∧␈↓9)␈↓ αt ␈↓↓(A=A ∨ A=B) ∧ ∀x.(x=A ⊃ isblock x)  ⊃  ∀x.(isblock x ⊃ x=A)␈↓,

␈↓ α∧␈↓which simplifies to

␈↓ α∧␈↓10)␈↓ αt ␈↓↓isblock A ⊃ ∀x.(isblock x ⊃ x=A)␈↓

␈↓ α∧␈↓and

␈↓ α∧␈↓11)␈↓ αt ␈↓↓(B=A ∨ B=B) ∧ ∀x.(x=B ⊃ isblock x)  ⊃  ∀x.(isblock x ⊃ x=B)␈↓,

␈↓ α∧␈↓which simplifies to

␈↓ α∧␈↓12)␈↓ αt ␈↓↓isblock B ⊃ ∀x.(isblock x ⊃ x=B)␈↓.

␈↓ α∧␈↓(10), (12) and (7) yield

␈↓ α∧␈↓13)␈↓ αt ␈↓↓∀x.(isblock x ⊃ x=A) ∨ ∀x.(isblock x ⊃ x=B)␈↓,

␈↓ α∧␈↓which asserts that either ␈↓↓A␈↓ is the only block or ␈↓↓B␈↓ is the only block.

␈↓ α∧␈↓␈↓ αT3.␈α
Consider␈αthe␈α
following␈α
algebraic␈αaxioms␈α
for␈α
natural␈αnumbers,␈α
i.e.␈α
non-negative␈αintegers,
␈↓ α∧␈↓appropriate when we aren't supposing that natural numbers are the only objects.

␈↓ α∧␈↓14)␈↓ αt ␈↓↓isnatnum 0 ∧ ∀x.(isnatnum x ⊃ isnatnum succ x)␈↓.

␈↓ α∧␈↓Circumscribing ␈↓↓isnatnum␈↓ in (14) yields
␈↓ α∧␈↓␈↓ u8


␈↓ α∧␈↓15)␈↓ αt ␈↓↓␈↓	F␈↓↓(0) ∧ ∀x.(␈↓	F␈↓↓(x) ⊃ ␈↓	F␈↓↓(succ x)) ∧ ∀x.(␈↓	F␈↓↓(x) ⊃ isnatnum x)  ⊃  ∀x.(isnatnum x ⊃ ␈↓	F␈↓↓(x))␈↓.

␈↓ α∧␈↓(15)␈αasserts␈α
that␈αthe␈αonly␈α
natural␈αnumbers␈αare␈α
those␈αobjects␈α
that␈α(14)␈αforces␈α
to␈αbe␈αnatural␈α
numbers,
␈↓ α∧␈↓and␈α
this␈α
is␈α
essentially␈α
the␈α
usual␈α
axiom␈α
schema␈α
of␈α
induction.␈α
 We␈α
can␈α
get␈α
closer␈α
to␈α
the␈α
usual␈α
schema
␈↓ α∧␈↓by␈α⊃substituting␈α∩␈↓↓␈↓	F␈↓↓(x) ≡ ␈↓	Y␈↓↓(x) ∧ isnatnum x␈↓.␈α⊃ This␈α⊃and␈α∩(14)␈α⊃make␈α⊃the␈α∩second␈α⊃conjunct␈α∩drop␈α⊃out
␈↓ α∧␈↓giving

␈↓ α∧␈↓16)␈↓ αt ␈↓↓␈↓	Y␈↓↓(0) ∧ ∀x.(␈↓	Y␈↓↓(x) ⊃ ␈↓	Y␈↓↓(succ x)) ⊃ ∀x.(isnatnum x ⊃ ␈↓	Y␈↓↓(x))␈↓.

␈↓ α∧␈↓␈↓ αT4.␈α
Returning␈α
to␈αthe␈α
blocks␈α
world,␈αsuppose␈α
we␈α
have␈α
a␈αpredicate␈α
␈↓↓on(x,y,s)␈↓␈α
asserting␈αthat␈α
block
␈↓ α∧␈↓␈↓↓x␈↓␈αis␈αon␈αblock␈α␈↓↓y␈↓␈αin␈αsituation␈α␈↓↓s.␈↓␈αSuppose␈αwe␈αhave␈αanother␈αpredicate␈α␈↓↓above(x,y,s)␈↓␈αwhich␈αasserts␈αthat
␈↓ α∧␈↓block ␈↓↓x␈↓ is above block ␈↓↓y␈↓ in situation ␈↓↓s.␈↓ We may write

␈↓ α∧␈↓17)␈↓ αt ␈↓↓∀x y s.(on(x,y,s) ⊃ above(x,y,s))␈↓

␈↓ α∧␈↓and

␈↓ α∧␈↓18)␈↓ αt ␈↓↓∀x y z s.(above(x,y,s) ∧ above(y,z,s) ⊃ above(x,z,s))␈↓,

␈↓ α∧␈↓i.e. ␈↓↓above␈↓ is a transitive relation.  Circumscribing ␈↓↓above␈↓ in (17)∧(18) gives

␈↓ α∧␈↓19)␈↓ αt ␈↓ β∀␈↓↓∀x y s.(on(x,y,s) ⊃ ␈↓	F␈↓↓(x,y,s))
␈↓ α∧␈↓↓␈↓ αy∧ ␈↓ β∀∀x y z s.(␈↓	F␈↓↓(x,y,s) ∧ ␈↓	F␈↓↓(y,z,s) ⊃ ␈↓	F␈↓↓(x,z,s))
␈↓ α∧␈↓↓␈↓ αy∧ ␈↓ β∀∀x y s.(␈↓	F␈↓↓(x,y,s) ⊃ above(x,y,s))
␈↓ α∧␈↓↓␈↓ ∧4⊃ ∀x y s.(above(x,y,s) ⊃ ␈↓	F␈↓↓(x,y,s))␈↓

␈↓ α∧␈↓which tells us that ␈↓↓above␈↓ is the transitive closure of ␈↓↓on.␈↓

␈↓ α∧␈↓␈↓ αTIn␈α∞the␈α∞preceding␈α
two␈α∞examples,␈α∞the␈α
schemas␈α∞produced␈α∞by␈α
circumscription␈α∞play␈α∞the␈α∞role␈α
of
␈↓ α∧␈↓axiom schemas rather than being just conjectures.



␈↓ α∧␈↓5. ␈↓αDomain Circumscription␈↓

␈↓ α∧␈↓␈↓ αTThe␈α∞form␈α∂of␈α∞circumscription␈α∂described␈α∞in␈α∞this␈α∂paper␈α∞generalizes␈α∂an␈α∞earlier␈α∂version␈α∞called
␈↓ α∧␈↓␈↓↓minimal␈α
inference␈↓.␈α Minimal␈α
inference␈αhas␈α
a␈αsemantic␈α
counterpart␈αcalled␈α
␈↓↓minimal␈α
entailment␈↓,␈αand
␈↓ α∧␈↓both␈α
are␈α
discussed␈α
in␈α
(McCarthy␈α
1977)␈α
and␈αmore␈α
extensively␈α
in␈α
(Davis␈α
1980).␈α
 The␈α
general␈αidea␈α
of
␈↓ α∧␈↓minimal␈αentailment␈αis␈αthat␈αa␈αsentence␈α␈↓↓q␈↓␈αis␈αminimally␈αentailed␈αby␈αan␈αaxiom␈α␈↓↓A,␈↓␈αwritten␈α␈↓↓A ␈↓πq␈↓↓␈↓βm␈↓↓ q␈↓,␈αif␈α␈↓↓q␈↓
␈↓ α∧␈↓is␈α∞true␈α∞in␈α∞all␈α∞␈↓↓minimal␈α∞models␈↓␈α∞of␈α∞␈↓↓A,␈↓␈α∞where␈α∞one␈α∞model␈α∞if␈α∞is␈α∞considered␈α∞less␈α∞than␈α∞another␈α∂if␈α∞they
␈↓ α∧␈↓agree␈α
on␈α
common␈α
elements,␈α
but␈α
the␈α
domain␈αof␈α
the␈α
larger␈α
many␈α
contain␈α
elements␈α
not␈α
in␈αthe␈α
domain
␈↓ α∧␈↓of␈α⊃the␈α⊃smaller.␈α⊃ We␈α⊃shall␈α⊃call␈α⊃the␈α⊃earlier␈α⊃form␈α⊃␈↓↓domain␈α⊃circumscription␈↓␈α⊃to␈α⊃contrast␈α⊃it␈α⊃with␈α⊂the
␈↓ α∧␈↓␈↓↓predicate circumscription␈↓ discussed in this paper.

␈↓ α∧␈↓␈↓ αTThe domain circumscription of the sentence ␈↓↓A␈↓ is the sentence

␈↓ α∧␈↓20)␈↓ αt ␈↓↓Axiom(␈↓	F␈↓↓) ∧ A␈↓#
␈↓	␈↓#
F␈↓↓␈↓#
␈↓# ⊃ ∀x.␈↓	F␈↓↓(x)␈↓,

␈↓ α∧␈↓where␈α␈↓↓A␈↓#
␈↓	␈↓#
F␈↓↓␈↓#
␈↓#␈↓␈α
is␈αthe␈αrelativization␈α
of␈α␈↓↓A␈↓␈αwith␈α
respect␈αto␈α␈↓	F␈↓␈α
and␈αis␈αformed␈α
by␈αreplacing␈α
each␈αuniversal
␈↓ α∧␈↓␈↓ u9


␈↓ α∧␈↓quantifier␈α
␈↓↓∀x.␈↓␈α
in␈α∞␈↓↓A␈↓␈α
by␈α
␈↓↓∀x.␈↓	F␈↓↓(x) ⊃␈↓␈α∞and␈α
each␈α
existential␈α
quantifier␈α∞␈↓↓∃x.␈↓␈α
by␈α
␈↓↓∃x.␈↓	F␈↓↓(x) ∧␈↓.␈α∞ ␈↓↓Axiom(␈↓	F␈↓↓)␈↓␈α
is
␈↓ α∧␈↓the␈α∞conjunction␈α∞of␈α∞sentences␈α
␈↓↓␈↓	F␈↓↓(a)␈↓␈α∞for␈α∞each␈α∞constant␈α
␈↓↓a␈↓␈α∞and␈α∞sentences␈α∞␈↓↓∀x.(␈↓	F␈↓↓(x) ⊃ ␈↓	F␈↓↓(f(x)))␈↓␈α∞for␈α
each
␈↓ α∧␈↓function symbol ␈↓↓f␈↓ and the corresponding sentences for functions of higher arities.

␈↓ α∧␈↓␈↓ αTDomain␈αcircumscription␈αcan␈αbe␈αreduced␈αto␈αpredicate␈αcircumscription␈αby␈αrelativizing␈α
␈↓↓A␈↓␈αwith
␈↓ α∧␈↓respect␈αto␈αa␈αnew␈αone␈αplace␈αpredicate␈αcalled␈α(say)␈α␈↓↓all,␈↓␈αthen␈αcircumscribing␈α␈↓↓all␈↓␈αin␈α␈↓↓A␈↓#
all␈↓# ∧ Axiom(all)␈↓,
␈↓ α∧␈↓thus getting

␈↓ α∧␈↓21)␈↓ αt ␈↓↓Axiom(␈↓	F␈↓↓) ∧ A␈↓#
␈↓	␈↓#
F␈↓↓␈↓#
␈↓# ∧ ∀x.(␈↓	F␈↓↓(x) ⊃ all(x))  ⊃  ∀x.(all(x) ⊃ ␈↓	F␈↓↓(x))␈↓.

␈↓ α∧␈↓Now␈αwe␈αjustify␈αour␈αusing␈αthe␈αname␈α␈↓↓all␈↓␈αby␈αadding␈αthe␈αaxiom␈α␈↓↓∀x.all(x)␈↓␈αso␈αthat␈α(21)␈αthen␈αsimplifies
␈↓ α∧␈↓precisely to (20).

␈↓ α∧␈↓␈↓ αTIn␈αthe␈αcase␈αof␈αthe␈αnatural␈αnumbers,␈αthe␈αdomain␈αcircumscription␈αof␈α␈↓αtrue␈↓,␈αthe␈αidentically␈αtrue
␈↓ α∧␈↓sentence,␈αagain␈αleads␈αto␈αthe␈αaxiom␈αschema␈αof␈αinduction.␈α Here␈α␈↓↓Axiom␈↓␈αdoes␈αall␈αthe␈αwork,␈αbecause␈αit
␈↓ α∧␈↓asserts that 0 is in the domain and that the domain is closed under the successor operation.



␈↓ α∧␈↓6. ␈↓αThe Model Theory of Predicate Circumscription␈↓

␈↓ α∧␈↓␈↓ αTThis␈αtreatment␈αis␈αsimilar␈αto␈αDavis's␈α(1980)␈αtreatment␈αof␈αdomain␈αcircumscription.␈α Pat␈αHayes
␈↓ α∧␈↓(1979) pointed out that the same ideas would work.

␈↓ α∧␈↓␈↓ αTThe␈α
intuitive␈α
idea␈α
of␈α
circumscription␈α
is␈α
saying␈α
that␈α
a␈α
tuple␈α
␈↓¬␈↓x␈α
satisfies␈α
the␈α
predicate␈α
␈↓↓P␈↓␈α
only␈α
if
␈↓ α∧␈↓it␈αhas␈αto.␈α It␈αhas␈αto␈αsatisfy␈α␈↓↓P␈↓␈αif␈αthis␈αfollows␈αfrom␈αthe␈αsentence␈α␈↓↓A.␈↓␈αThe␈αmodel-theoretic␈αcounterpart
␈↓ α∧␈↓of␈αcircumscription␈αis␈α␈↓↓minimal␈αentailment␈↓.␈α A␈αsentence␈α␈↓↓q␈↓␈α
is␈αminimally␈αentailed␈αby␈α␈↓↓A,␈↓␈αiff␈α␈↓↓q␈↓␈αis␈αtrue␈α
in
␈↓ α∧␈↓all␈α∂minimal␈α∂models␈α∂of␈α∂␈↓↓A,␈↓␈α∂where␈α∞a␈α∂model␈α∂is␈α∂minimal␈α∂if␈α∂as␈α∞few␈α∂as␈α∂possible␈α∂tuples␈α∂␈↓¬␈↓x␈α∂satisfy␈α∞the
␈↓ α∧␈↓predicate ␈↓↓P.␈↓ More formally, this works out as follows.

␈↓ α∧␈↓␈↓αDefinition:␈αLet␈α␈↓↓M(A)␈↓α␈αand␈α␈↓↓N(A)␈↓α␈αbe␈αmodels␈αof␈αthe␈αsentence␈α␈↓↓A.␈↓α␈αWe␈αsay␈αthat␈α␈↓↓M␈↓α␈αis␈αa␈αsubmodel␈αof
␈↓ α∧␈↓α␈↓↓N␈↓α␈αin␈α
␈↓↓P,␈↓α␈αwriting␈α
␈↓↓M ≤␈↓βP␈↓↓ N␈↓α,␈αif␈α
␈↓↓M␈↓α␈αand␈α
␈↓↓N␈↓α␈αhave␈α
the␈αsame␈α
domain,␈αall␈α
other␈αpredicate␈α
symbols␈αin␈α
␈↓↓A␈↓α
␈↓ α∧␈↓αbesides␈α␈↓↓P␈↓α␈αhave␈αthe␈αsame␈αextensions␈αin␈α␈↓↓M␈↓α␈αand␈α␈↓↓N,␈↓α␈αbut␈αthe␈αextension␈αof␈α␈↓↓P␈↓α␈αin␈α␈↓↓M␈↓α␈αis␈αincluded␈αin
␈↓ α∧␈↓αits extension in ␈↓↓N.␈↓α

␈↓ α∧␈↓αDefinition:␈α
A␈α
model␈α
␈↓↓M␈↓α␈αof␈α
␈↓↓A␈↓α␈α
is␈α
called␈αminimal␈α
in␈α
␈↓↓P␈↓α␈α
iff␈α␈↓↓M' ≤␈↓βP␈↓↓ M␈↓␈α
only␈α
if␈α
␈↓↓M' = M␈↓.␈α As␈α
discussed
␈↓ α∧␈↓by Davis (1980), minimal models don't always exist.

␈↓ α∧␈↓␈↓αDefinition:␈αWe␈αsay␈αthat␈α␈↓↓A␈↓α␈αminimally␈αentails␈α␈↓↓q␈↓α␈αwith␈αrespect␈αto␈α␈↓↓P,␈↓α␈αwritten␈α␈↓↓A ␈↓πq␈↓↓␈↓βP␈↓↓ q␈↓α␈αprovided␈α␈↓↓q␈↓α␈α
is
␈↓ α∧␈↓αtrue in all models of ␈↓↓A␈↓α that are minimal in ␈↓↓P.␈↓α

␈↓ α∧␈↓αTheorem:␈α
Any␈α
instance␈α
of␈α
the␈α
circumscription␈α
of␈α
␈↓↓P␈↓α␈αin␈α
␈↓↓A␈↓α␈α
is␈α
true␈α
in␈α
all␈α
models␈α
of␈α
␈↓↓A␈↓α␈αminimal␈α
in
␈↓ α∧␈↓α␈↓↓P,␈↓α i.e. is minimally entailed by ␈↓↓A␈↓α in ␈↓↓P␈↓.

␈↓ α∧␈↓Proof:␈αLet␈α␈↓↓M␈↓␈αbe␈αa␈αmodel␈αof␈α␈↓↓A␈↓␈αminimal␈αin␈α␈↓↓P.␈↓␈αLet␈α␈↓↓P'␈↓␈αbe␈αa␈αpredicate␈αsatisfying␈αthe␈αleft␈αside␈αof␈α(1)
␈↓ α∧␈↓when␈α
substituted␈αfor␈α
␈↓	F␈↓.␈α By␈α
the␈αsecond␈α
conjunct␈αof␈α
the␈αleft␈α
side␈α␈↓↓P␈↓␈α
is␈αan␈α
extension␈αof␈α
␈↓↓P'.␈↓␈α
If␈αthe
␈↓ α∧␈↓right␈αside␈αof␈α(1)␈α
were␈αnot␈αsatisfied,␈α␈↓↓P␈↓␈αwould␈α
be␈αa␈αproper␈αextension␈αof␈α
␈↓↓P'.␈↓␈αIn␈αthat␈αcase,␈α
we␈αcould
␈↓ α∧␈↓get␈αa␈α
proper␈αsubmodel␈α
␈↓↓M'␈↓␈αof␈α␈↓↓M␈↓␈α
by␈αletting␈α
␈↓↓M'␈↓␈αagree␈α
with␈α␈↓↓M␈↓␈αon␈α
all␈αpredicates␈α
except␈α␈↓↓P␈↓␈αand␈α
agree
␈↓ α∧␈↓with ␈↓↓P'␈↓ on ␈↓↓P.␈↓ This would contradict the assumed minimality of ␈↓↓M.␈↓
␈↓ α∧␈↓␈↓ f10


␈↓ α∧␈↓␈↓αCorollary: If ␈↓↓A ␈↓πr␈↓↓␈↓βP␈↓↓ q␈↓α, then ␈↓↓A ␈↓πq␈↓↓␈↓βP␈↓↓ q␈↓.

␈↓ α∧␈↓␈↓ αTWhile␈α⊂we␈α⊂have␈α∂discussed␈α⊂minimal␈α⊂entailment␈α∂in␈α⊂a␈α⊂single␈α∂predicate␈α⊂␈↓↓P,␈↓␈α⊂the␈α⊂relation␈α∂␈↓↓<␈↓βP,Q␈↓,
␈↓ α∧␈↓models␈α∩minimal␈α∩in␈α∩␈↓↓P␈↓␈α∩and␈α∩␈↓↓Q,␈↓␈α⊃and␈α∩␈↓↓␈↓πq␈↓↓␈↓βP,Q␈↓␈α∩have␈α∩corresponding␈α∩properties␈α∩and␈α∩a␈α⊃corresponding
␈↓ α∧␈↓relation to the syntactic notion ␈↓↓␈↓πr␈↓↓␈↓βP,Q␈↓ mentioned earlier.



␈↓ α∧␈↓7. ␈↓αMore on Blocks␈↓

␈↓ α∧␈↓␈↓ αTThe axiom

␈↓ α∧␈↓22)␈↓ αt ␈↓↓∀x y s.(∀z.¬prevents(z,move(x,y),s) ⊃ on(x,y,result(move(x,y),s)))␈↓

␈↓ α∧␈↓states␈α∂that␈α∂unless␈α∂something␈α∂prevents␈α∞it,␈α∂␈↓↓x␈↓␈α∂is␈α∂on␈α∂␈↓↓y␈↓␈α∂in␈α∞the␈α∂situation␈α∂that␈α∂results␈α∂from␈α∂the␈α∞action
␈↓ α∧␈↓␈↓↓move(x,y).␈↓

␈↓ α∧␈↓We now list various "things" that may prevent this action.

␈↓ α∧␈↓23)␈↓ αt ␈↓↓∀x y s.(¬isblock x ∨ ¬isblock y ⊃ prevents(NONBLOCK,move(x,y),s))␈↓

␈↓ α∧␈↓24)␈↓ αt ␈↓↓∀x y s.(¬clear(x,s) ∨ ¬clear(y,s) ⊃ prevents(COVERED,move(x,y),s))␈↓

␈↓ α∧␈↓25)␈↓ αt ␈↓↓∀x y s.(tooheavy x ⊃ prevents(weight x,move(x,y),s))␈↓.

␈↓ α∧␈↓␈↓ αTLet␈αus␈αnow␈αsuppose␈αthat␈αa␈αheuristic␈αprogram␈αwould␈αlike␈αto␈αmove␈αblock␈α␈↓↓A␈↓␈αonto␈αblock␈α␈↓↓C␈↓␈αin␈αa
␈↓ α∧␈↓situation␈α␈↓↓s0.␈↓␈αThe␈αprogram␈αshould␈αconjecture␈αfrom␈α(22)␈αthat␈αthe␈αaction␈α␈↓↓move(A,C)␈↓␈αwould␈αhave␈αthe
␈↓ α∧␈↓desired␈α~effect,␈α~so␈α~it␈α~must␈α~try␈α~to␈α~establish␈α~␈↓↓∀z.¬prevents(z,move(A,C),s0).␈↓␈α~The␈α→predicate
␈↓ α∧␈↓␈↓↓λz.prevents(z,move(A,C),s0)␈↓␈α∞can␈α∂be␈α∞circumscribed␈α∂in␈α∞the␈α∞conjunction␈α∂of␈α∞the␈α∂sentences␈α∞resulting
␈↓ α∧␈↓from specializing (23), (24) and (25), and this gives

␈↓ α∧␈↓26)␈↓ αt␈↓ β∀␈↓↓(¬isblock A ∨ ¬isblock C ⊃ ␈↓	F␈↓↓(NONBLOCK))
␈↓ α∧␈↓↓␈↓ αy∧ ␈↓ β∀(¬clear(A,s0) ∨ ¬clear(C,s0) ⊃ ␈↓	F␈↓↓(COVERED))
␈↓ α∧␈↓↓␈↓ αy∧ ␈↓ β∀(tooheavy A ⊃ ␈↓	F␈↓↓(weight A))
␈↓ α∧␈↓↓␈↓ αy∧ ␈↓ β∀∀z.(␈↓	F␈↓↓(z) ⊃ prevents(z,move(A,C),s0))
␈↓ α∧␈↓↓␈↓ βd⊃ ∀z.(prevents(z,move(A,C),s0) ⊃ ␈↓	F␈↓↓(z))␈↓

␈↓ α∧␈↓which␈αsays␈αthat␈αthe␈αonly␈α
things␈αthat␈αcan␈αprevent␈αthe␈α
move␈αare␈αthe␈αphenomena␈αdescribed␈α
in␈α(23),
␈↓ α∧␈↓(24)␈α∞and␈α∂(25).␈α∞ Whether␈α∞(26)␈α∂is␈α∞true␈α∞depends␈α∂on␈α∞how␈α∞good␈α∂the␈α∞program␈α∞was␈α∂in␈α∞finding␈α∂all␈α∞the
␈↓ α∧␈↓relevant␈αstatements.␈α Since␈αthe␈αprogram␈α
wants␈αto␈αshow␈αthat␈αnothing␈α
prevents␈αthe␈αmove,␈αit␈αmust␈α
set
␈↓ α∧␈↓␈↓↓∀z.(␈↓	F␈↓↓(z) ≡ false)␈↓, after which (26) simplifies to

␈↓ α∧␈↓27)␈↓ αt␈↓ β∀␈↓↓(isblock A ∧ isblock B ∧ clear(A,s0) ∧ clear(B,s0) ∧ ¬tooheavy A
␈↓ α∧␈↓↓␈↓ βd⊃ ∀z.¬prevents(z,move(A,C),s0)␈↓.

␈↓ α∧␈↓We suppose that the premisses of this implication are to be obtained as follows:

␈↓ α∧␈↓␈↓ αT1. ␈↓↓isblock A␈↓ and ␈↓↓isblock B␈↓ are explicitly asserted.
␈↓ α∧␈↓␈↓ f11


␈↓ α∧␈↓␈↓ αT2.␈α∂Suppose␈α∞that␈α∂the␈α∂only␈α∞␈↓↓on␈↓ness␈α∂assertion␈α∞explicitly␈α∂given␈α∂for␈α∞situation␈α∂␈↓↓s0␈↓␈α∂is␈α∞␈↓↓on(A,B,s0).␈↓
␈↓ α∧␈↓Circumscription of ␈↓↓λx y.on(x,y,s0)␈↓ in this assertion gives

␈↓ α∧␈↓28)␈↓ αt ␈↓↓␈↓	F␈↓↓(A,B) ∧ ∀x y.(␈↓	F␈↓↓(x,y) ⊃ on(x,y,s0))  ⊃  ∀x y.(on(x,y,s0) ⊃ ␈↓	F␈↓↓(x,y))␈↓,

␈↓ α∧␈↓and taking ␈↓↓␈↓	F␈↓↓(x,y) ≡ x=A ∧ y=B␈↓ yields

␈↓ α∧␈↓29)␈↓ αt ␈↓↓∀x y.(on(x,y,s0) ⊃ x=A ∧ y=B)␈↓.

␈↓ α∧␈↓Using

␈↓ α∧␈↓30)␈↓ αt ␈↓↓∀x s.(clear(x,s) ≡ ∀y.¬on(y,x,s))␈↓

␈↓ α∧␈↓as the definition of ␈↓↓clear␈↓ yields the second two desired premisses.

␈↓ α∧␈↓␈↓ αT3.␈α_␈↓↓¬tooheavy(x)␈↓␈α_might␈α→be␈α_explicitly␈α_present␈α→or␈α_it␈α_might␈α→also␈α_be␈α_conjectured␈α→by␈α_a
␈↓ α∧␈↓circumscription assuming that if ␈↓↓x␈↓ were too heavy, the facts would establish it.

␈↓ α∧␈↓␈↓ αTCircumscription␈α∃may␈α⊗also␈α∃be␈α⊗convenient␈α∃for␈α∃asserting␈α⊗that␈α∃when␈α⊗a␈α∃block␈α⊗is␈α∃moved,
␈↓ α∧␈↓everything␈α∞that␈α∞cannot␈α∞be␈α∞proved␈α∂to␈α∞move␈α∞stays␈α∞where␈α∞it␈α∂was.␈α∞ In␈α∞the␈α∞simple␈α∞blocks␈α∂world,␈α∞the
␈↓ α∧␈↓effect␈αof␈αthis␈αcan␈αeasily␈αbe␈αachieved␈αby␈αan␈αaxiom␈αthat␈αstates␈αthat␈αall␈αblocks␈αexcept␈αthe␈αone␈αthat␈αis
␈↓ α∧␈↓moved␈αstay␈αput.␈α However,␈αif␈αthere␈αare␈αvarious␈αsentences␈αthat␈αsay␈α(for␈αexample)␈αthat␈αone␈αblock␈αis
␈↓ α∧␈↓attached to another, circumscription may express the heuristic situation better than an axiom.



␈↓ α∧␈↓8. ␈↓αRemarks and Acknowledgements␈↓

␈↓ α∧␈↓␈↓ αT1.␈αCircumscription␈αis␈αnot␈α
a␈α"non-monotonic␈αlogic".␈α It␈α
is␈αa␈αform␈αof␈αnon-monotonic␈α
reasoning
␈↓ α∧␈↓augmenting␈αordinary␈αfirst␈αorder␈αlogic.␈α Of␈αcourse,␈αsentence␈αschemata␈αare␈αnot␈αproperly␈αhandled␈αby
␈↓ α∧␈↓most␈α
present␈α
general␈α
purpose␈α
resolution␈α
theorem␈α
provers.␈α
 Even␈α
fixed␈α
schemata␈α
of␈α
mathematical
␈↓ α∧␈↓induction␈αwhen␈αused␈αfor␈αproving␈αprograms␈αcorrect␈αusually␈αrequire␈αhuman␈αintervention␈αor␈αspecial
␈↓ α∧␈↓heuristics,␈αwhile␈αhere␈αthe␈αprogram␈αwould␈αhave␈αto␈αuse␈αnew␈αschemata␈αproduced␈αby␈αcircumscription.
␈↓ α∧␈↓In␈α
(McCarthy␈α
1979b)␈α
we␈α
treat␈α
some␈α
modalities␈α∞in␈α
first␈α
order␈α
logic␈α
instead␈α
of␈α
in␈α
modal␈α∞logic.␈α
 In
␈↓ α∧␈↓our␈α∞opinion,␈α∞it␈α∞is␈α∞better␈α∞to␈α∞avoid␈α∞modifying␈α∞the␈α∞logic␈α∞if␈α∞at␈α∞all␈α∞possible,␈α∞because␈α∞there␈α∞are␈α∞many
␈↓ α∧␈↓temptations to modify the logic, and it would be very difficult to keep them compatible.

␈↓ α∧␈↓␈↓ αT2.␈α
The␈αdefault␈α
case␈αreasoning␈α
provided␈αin␈α
many␈αsystems␈α
is␈αless␈α
general␈αthan␈α
circumscription.
␈↓ α∧␈↓Suppose,␈α∞for␈α∞example,␈α∂that␈α∞a␈α∞block␈α∂␈↓↓x␈↓␈α∞is␈α∞considered␈α∂to␈α∞be␈α∞on␈α∂a␈α∞block␈α∞␈↓↓y␈↓␈α∂only␈α∞if␈α∞this␈α∂is␈α∞explicitly
␈↓ α∧␈↓stated,␈αi.e.␈αthe␈αdefault␈αis␈αthat␈α␈↓↓x␈↓␈αis␈αnot␈αon␈α␈↓↓y.␈↓␈αThen␈αfor␈αeach␈αindividual␈αblock␈α␈↓↓x,␈↓␈αwe␈αmay␈αbe␈αable␈αto
␈↓ α∧␈↓conclude␈α
that␈α
it␈α
isn't␈α
on␈α
block␈α
␈↓↓A,␈↓␈α
but␈α
we␈α
will␈α
not␈α
be␈α
able␈α
to␈α
conclude,␈α
as␈α∞circumscription␈α
would
␈↓ α∧␈↓allow,␈α
that␈α
there␈αare␈α
no␈α
blocks␈αon␈α
␈↓↓A.␈↓␈α
That␈α
would␈αrequire␈α
a␈α
separate␈αdefault␈α
statement␈α
that␈αa␈α
block
␈↓ α∧␈↓is clear unless something is stated to be on it.

␈↓ α∧␈↓␈↓ αT3.␈αThe␈αconjunct␈α␈↓↓∀␈↓¬␈↓↓x.(␈↓	F␈↓↓(␈↓¬␈↓↓x)␈α⊃␈αP(␈↓¬␈↓↓x))␈↓␈αin␈αthe␈αpremiss␈αof␈α(1)␈αis␈αthe␈αresult␈αof␈αsuggestions␈αby␈αAshok
␈↓ α∧␈↓Chandra␈α∩(August␈α∩1979)␈α∩and␈α∩Patrick␈α∩Hayes␈α∩(September␈α∩1979)␈α∩whom␈α∩I␈α∩thank␈α∩for␈α∪their␈α∩help.
␈↓ α∧␈↓Without␈α
it,␈α
circumscribing␈α
a␈α
disjunction,␈α
as␈α
in␈α
the␈α
second␈α
example␈α
in␈α
section␈α
4,␈α
would␈α
lead␈α
to␈α
a
␈↓ α∧␈↓contradiction.
␈↓ α∧␈↓␈↓ f12


␈↓ α∧␈↓␈↓ αT4.␈αThe␈α
most␈αdirect␈α
way␈αof␈αusing␈α
circumscription␈αin␈α
AI␈αis␈αin␈α
a␈αheuristic␈α
reasoning␈αprogram
␈↓ α∧␈↓that␈α∂represents␈α∞much␈α∂of␈α∞what␈α∂it␈α∞believes␈α∂by␈α∞sentences␈α∂of␈α∞logic.␈α∂ The␈α∞program␈α∂would␈α∞sometimes
␈↓ α∧␈↓apply␈α
circumscription␈α
to␈α
certain␈α
predicates␈α
in␈αsentences.␈α
 In␈α
particular,␈α
when␈α
it␈α
wants␈α
to␈αperform
␈↓ α∧␈↓an␈α∞action␈α∞that␈α∞might␈α
be␈α∞prevented␈α∞by␈α∞something,␈α∞it␈α
circumscribes␈α∞the␈α∞prevention␈α∞predicate␈α∞in␈α
a
␈↓ α∧␈↓sentence ␈↓↓A␈↓ representing the information being taken into account.

␈↓ α∧␈↓␈↓ αTClearly␈α∞the␈α∞program␈α∂will␈α∞have␈α∞to␈α∞include␈α∂domain␈α∞dependent␈α∞heuristics␈α∞for␈α∂deciding␈α∞what
␈↓ α∧␈↓circumscriptions to make and when to take them back.

␈↓ α∧␈↓␈↓ αT5.␈αIn␈αcircumscription␈αit␈αdoes␈αno␈αharm␈αto␈αtake␈αirrelevant␈αfacts␈αinto␈αaccount.␈α If␈αthese␈αfacts␈αdo
␈↓ α∧␈↓not␈α∞contain␈α∞the␈α∞predicate␈α∞symbol␈α∞being␈α∞circumscribed,␈α∞they␈α∞will␈α∞appear␈α∞as␈α∞conjuncts␈α∞on␈α∞the␈α∞left
␈↓ α∧␈↓side␈αof␈αthe␈αimplication␈αunchanged.␈α Therefore,␈αthe␈αoriginal␈αversions␈αof␈αthese␈αfacts␈αcan␈αbe␈αused␈αin
␈↓ α∧␈↓proving the left side.

␈↓ α∧␈↓␈↓ αT6.␈α⊂Circumscription␈α⊂can␈α⊂be␈α⊂used␈α⊂in␈α⊂other␈α⊂formalisms␈α⊂than␈α⊂first␈α⊂order␈α⊂logic.␈α⊂ Suppose␈α∂for
␈↓ α∧␈↓example␈α
that␈α
a␈α
set␈α
␈↓↓a␈↓␈α
satisfies␈α
a␈α
formula␈α
␈↓↓A(a)␈↓␈α
of␈α
set␈α
theory.␈α
 The␈α
circumscription␈α
of␈α
this␈α
formula
␈↓ α∧␈↓can be taken to be

␈↓ α∧␈↓31)␈↓ αt ␈↓↓∀x.(A(x) ∧ (x ⊂ a) ⊃ (a ⊂ x))␈↓.

␈↓ α∧␈↓If␈α␈↓↓a␈↓␈αoccurs␈αin␈α␈↓↓A(a)␈↓␈αonly␈αin␈αexpressions␈αof␈αthe␈αform␈α␈↓↓z␈αε␈αa␈↓,␈αthen␈αits␈αmathematical␈αproperties␈αshould
␈↓ α∧␈↓be␈α⊃analogous␈α⊃to␈α∩those␈α⊃of␈α⊃predicate␈α∩circumscription.␈α⊃ We␈α⊃have␈α∩not␈α⊃explored␈α⊃what␈α∩happens␈α⊃if
␈↓ α∧␈↓formulas like ␈↓↓a ε z␈↓ occur.

␈↓ α∧␈↓␈↓ αT7.␈α
The␈αresults␈α
of␈αcircumscription␈α
depend␈αon␈α
the␈αset␈α
of␈αpredicates␈α
used␈αto␈α
express␈α
the␈αfacts.
␈↓ α∧␈↓For␈α
example,␈α
the␈αsame␈α
facts␈α
about␈αthe␈α
blocks␈α
world␈αcan␈α
be␈α
axiomatized␈αusing␈α
the␈α
relation␈α
␈↓↓on␈↓␈αor
␈↓ α∧␈↓the␈αrelation␈α␈↓↓above␈↓␈αconsidered␈αin␈αsection␈α4␈αor␈αalso␈αin␈αterms␈αof␈αthe␈αheights␈αand␈αhorizontal␈αpositions
␈↓ α∧␈↓of␈αthe␈αblocks.␈α Since␈αthe␈αresults␈αof␈αcircumscription␈αwill␈αdiffer␈αaccording␈αto␈αwhich␈αrepresentation␈αis
␈↓ α∧␈↓chosen,␈α≥we␈α≤see␈α≥that␈α≤the␈α≥choice␈α≤of␈α≥representation␈α≤has␈α≥epistemological␈α≥consequences␈α≤if
␈↓ α∧␈↓circumscription␈α∞is␈α∂admitted␈α∞as␈α∂a␈α∞rule␈α∞of␈α∂conjecture.␈α∞ Choosing␈α∂the␈α∞set␈α∞of␈α∂predicates␈α∞in␈α∂terms␈α∞of
␈↓ α∧␈↓which␈α∂to␈α∂axiomatize␈α∂as␈α∂set␈α∂of␈α∂facts,␈α∂such␈α∂as␈α∂those␈α∂about␈α∂blocks,␈α∂is␈α∂like␈α∂choosing␈α⊂a␈α∂co-ordinate
␈↓ α∧␈↓system␈αin␈αphysics␈αor␈αgeography.␈α As␈α
discussed␈αin␈α(McCarthy␈α1979a),␈αcertain␈αconcepts␈αare␈α
definable
␈↓ α∧␈↓only␈αrelative␈αto␈α
a␈αtheory.␈α What␈α
theory␈αadmits␈αthe␈α
most␈αuseful␈αkinds␈α
of␈αcircumscription␈αmay␈αbe␈α
an
␈↓ α∧␈↓important␈α
criterion␈α
in␈αthe␈α
choice␈α
of␈α
predicates.␈α It␈α
may␈α
also␈α
be␈αpossible␈α
to␈α
make␈α
some␈αstatements
␈↓ α∧␈↓about a domain like the blocks world in a form that does not depend on the language used.

␈↓ α∧␈↓␈↓ αT8.␈α⊃This␈α⊃investigation␈α⊃was␈α∩supported␈α⊃in␈α⊃part␈α⊃by␈α⊃ARPA␈α∩Contract␈α⊃MDA-903-76-C-0206,
␈↓ α∧␈↓ARPA␈α∩Order␈α∩No.␈α∩2494,␈α∩in␈α∩part␈α∩by␈α∩NSF␈α∩Grant␈α∩MCS␈α∩78-00524,␈α∩in␈α∩part␈α∩by␈α∩the␈α∩IBM␈α∩1979
␈↓ α∧␈↓Distinguished␈α
Faculty␈α
Program␈αat␈α
the␈α
T.␈α
J.␈αWatson␈α
Research␈α
Center,␈α
and␈αin␈α
part␈α
by␈α
the␈αCenter
␈↓ α∧␈↓for Advanced Study in the Behavioral Sciences.



␈↓ α∧␈↓9. ␈↓αReferences␈↓

␈↓ α∧␈↓␈↓αAmarel,␈αSaul␈α(1971)␈↓:␈α"On␈α
Representation␈αof␈αProblems␈αof␈α
Reasoning␈αabout␈αActions",␈αin␈α
D.␈αMichie
␈↓ α∧␈↓(ed.), ␈↓↓Machine Intelligence 3␈↓, Edinburgh University Press, pp. 131-171.

␈↓ α∧␈↓␈↓αChandra, Ashok (1979)␈↓: personal conversation, August.
␈↓ α∧␈↓␈↓ f13


␈↓ α∧␈↓␈↓αDavis,␈α∃Martin␈α∃(1980)␈↓:␈α∃"Notes␈α∃on␈α∀the␈α∃Mathematics␈α∃of␈α∃Non-Monotonic␈α∃Reasoning",␈α∀␈↓↓Artificial
␈↓ α∧␈↓↓Intelligence␈↓, this issue.

␈↓ α∧␈↓␈↓αHayes, Patrick (1979)␈↓: personal conversation, September.

␈↓ α∧␈↓␈↓αHewitt,␈α⊃Carl␈α∩(1972)␈↓:␈α⊃␈↓↓Description␈α∩and␈α⊃Theoretical␈α∩Analysis␈α⊃(Using␈α∩Schemata)␈α⊃of␈α∩PLANNER:␈α⊃a
␈↓ α∧␈↓↓Language␈αfor␈αProving␈αTheorems␈αand␈αManipulating␈αModels␈αin␈αa␈αRobot␈↓,␈αMIT␈αAI␈α
Laboratory␈αTR-
␈↓ α∧␈↓258.

␈↓ α∧␈↓␈↓αMcCarthy,␈α_John␈α_(1960)␈↓:␈α→"Programs␈α_with␈α_Common␈α→Sense",␈α_␈↓↓Proceedings␈α_of␈α→the␈α_Teddington
␈↓ α∧␈↓↓Conference on the Mechanization of Thought Processes␈↓, H.M.  Stationery Office, 1960.

␈↓ α∧␈↓␈↓αMcCarthy,␈α
John␈αand␈α
Patrick␈αHayes␈α
(1969)␈↓:␈α
"Some␈αPhilosophical␈α
Problems␈αfrom␈α
the␈αStandpoint␈α
of
␈↓ α∧␈↓Artificial␈α
Intelligence,"␈α∞in␈α
D.␈α
Michie␈α∞(ed),␈α
␈↓↓Machine␈α
Intelligence␈α∞4␈↓,␈α
American␈α
Elsevier,␈α∞New␈α
York,
␈↓ α∧␈↓NY.

␈↓ α∧␈↓␈↓αMcCarthy,␈α∂John␈α∂(1977)␈↓:␈α∂"Epistemological␈α∂Problems␈α∂of␈α∂Artificial␈α∂Intelligence",␈α∂␈↓↓Proceedings␈α∂of␈α∞the
␈↓ α∧␈↓↓Fifth International Joint Conference on Artificial Intelligence␈↓, M.I.T., Cambridge, MA.

␈↓ α∧␈↓␈↓αMcCarthy,␈αJohn␈α(1979a)␈↓:␈α
"Ascribing␈αMental␈αQualities␈α
to␈αMachines",␈α␈↓↓Philosophical␈α
Perspectives␈αin
␈↓ α∧␈↓↓Artificial Intelligence␈↓, Martin Ringle, ed., Harvester Press, July 1979.

␈↓ α∧␈↓␈↓αMcCarthy,␈α⊃John␈α⊃(1979b)␈↓:␈α⊃"First␈α⊃Order␈α⊃Theories␈α⊃of␈α⊃Individual␈α⊃Concepts␈α⊃and␈α⊃Propositions",␈α⊃in
␈↓ α∧␈↓Michie, Donald (ed.) ␈↓↓Machine Intelligence 9␈↓, University of Edinburgh Press.

␈↓ α∧␈↓␈↓αReiter, Raymond (1980)␈↓: "A Logic for Default Reasoning", ␈↓↓Artificial Intelligence␈↓, this issue.

␈↓ α∧␈↓␈↓αSussman,␈α⊃G.J.,␈α⊃T.␈α⊃Winograd,␈α⊃and␈α⊃E.␈α⊃Charniak␈α⊃(1971)␈↓:␈α⊃␈↓↓Micro-Planner␈α⊃Reference␈α⊃Manual,␈α⊂AI
␈↓ α∧␈↓↓Memo 203␈↓, M.I.T. AI Lab.

␈↓ α∧␈↓This version of CIRCUM.NEW[S79,JMC] PUBbed at 23:40 on October 3, 1979.